package com.ma.array.binary;

public class BinarySearch {
    public static void main(String[] args) {
        int[] nums = {10, 11, 12, 12, 12, 12, 12, 12, 13, 14, 15};
        int target = 12;
        System.out.println(BasicBinary.binarySearch(nums, target));
        System.out.println(BasicBinary.leftBound(nums, target));
        System.out.println(BasicBinary.rightBound(nums, target));

    }

    /* 1、最基本的二分查找算法：
           - 因为我们初始化 right = nums.length - 1
                所以决定了我们的「搜索区间」是 [left, right]
                所以决定了 while (left <= right)
                同时也决定了 left = mid+1 和 right = mid-1
           - 因为我们只需找到一个 target 的索引即可
                所以当 nums[mid] == target 时可以立即返回
     */
    private static int basicBinary(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        return -1;
    }

    /* 2、寻找左侧边界的二分查找
            - 因为我们初始化 right = nums.length
                所以决定了我们的「搜索区间」是 [left, right)
                所以决定了 while (left < right)
                同时也决定了 left = mid + 1 和 right = mid
            - 因为我们需找到 target 的最左侧索引
                所以当 nums[mid] == target 时不要立即返回
                而要收紧右侧边界以锁定左侧边界
     */

    private static int leftBound(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid;
            }
        }
        return left;
    }

    /* 3、寻找右侧边界的二分查找：
           -  因为我们初始化 right = nums.length
                所以决定了我们的「搜索区间」是 [left, right)
                所以决定了 while (left < right)
                同时也决定了 left = mid + 1 和 right = mid

           -  因为我们需找到 target 的最右侧索引
                所以当 nums[mid] == target 时不要立即返回
                而要收紧左侧边界以锁定右侧边界

           -  又因为收紧左侧边界时必须 left = mid + 1
                所以最后无论返回 left 还是 right，必须减一
     */
    public static int rightBound(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid;
            }
        }
        return left - 1;
    }

    static class BasicBinary {
        static int binarySearch(int[] nums, int target) {
            int left = 0, right = nums.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] < target) {
                    left = mid + 1;
                } else if (nums[mid] > target) {
                    right = mid - 1;
                } else if (nums[mid] == target) {
                    return mid;
                }
            }
            return -1;
        }

        static int leftBound(int[] nums, int target) {
            int left = 0, right = nums.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;

                if (nums[mid] < target) {
                    left = mid + 1;
                } else if (nums[mid] > target) {
                    right = mid - 1;
                } else if (nums[mid] == target) {
                    // 别返回，锁定左侧边界
                    right = mid - 1;
                }
            }
            if (left >= nums.length || nums[left] != target) {
                return -1;
            }
            return left;
        }


        static int rightBound(int[] nums, int target) {
            int left = 0, right = nums.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;

                if (nums[mid] < target) {
                    left = mid + 1;
                } else if (nums[mid] > target) {
                    right = mid - 1;
                } else if (nums[mid] == target) {
                    // 别返回，锁定右侧边界
                    left = mid + 1;
                }
            }
            if (right < 0 || nums[right] != target) {
                return -1;
            }
            return right;
        }
    }


}
